Sharding: Load-balancing
Ethereum
LayerX (minaminao.icon & nrryuya.icon)
Sangyeon Woo, Jeho Song, Sanghyeok Kim, Youngjae Kim & Sungyong Park (Sogang University)
Cluster Computing'20
Propose GARET: transaction load prediction algorithm and account relocation algorithm
Transaction load (gas) prediction: Average of the gas used in the past blocks in the shard with decay
Account reocation as multi-dimensional knapsack problem: Maximize the sum of (predicted_gas_usage / gas_limit) of each shard
Expperiment w/ 1,400 most recent transactions from Etherscan based on OMNeT++
Result: outperforms existing techniques by up to 12% in transaction throughput and decreases the makespan of transaction latency by about 74% under various conditions
Review by nrryuya.icon
This paper assumes that "assigns each account to a shard statically according to its address prefix" (called S-ACC), but this is not correct.
There is no consideration of gas overhead due to cross-shad transactions?
CBC Casper sharding
Related
Small threads on ethresear.ch
Others
Yuechen Tao (Hong Kong University of Science and Technology)
ICDE'20
Propose
an inter-shard merging algorithm with incentives to encourage small shards to merge with one another and form a larger shard
an intra-shard transaction selection mechanism to encourage miners to select different subsets of transactions for validation
a parameter unification method to further improve these two algorithms
Analyze our proposed algorithms using the game theoretic approach, and prove that they converge to a Nash Equilibrium.
Resists adversaries who occupy at most 33% of the computation power.
Implemented our designs on go-Ethereum 1.8.0 and evaluated their performance using both real-world blockchain transactions and large-scale simulations.
Results: throughput has been improved by 7.2×, and the number of empty blocks has been reduced by 90%.
Omniledger
Lan N. Nguyen (Univ.of Florida), Truc D. T. Nguyen, Thang N. Dinh, My T. Thai
IEEE ICDCS'19
Improve transaction placement strategy in UTXO-based sharding
Against the random placement strategy used in Omniledger and Rapidchain
Algorithm adopted by user-side softwares (e.g. wallets)
A set of transactions is presented as a directed graph (Transaction-as-Node (TaN) Network)
Calculate the Transaction-to-Shard (T2S) score; "fitness" between the new arrival transaction and shards with TaN network
Based on PageRank algorithm (w/ comparison to other graph partitioning algos including Metis and Greedy)
Calculate Latencyto-Shard (L2S) score
Finally, try to maximize the T2S-score while minimizing the L2S-score
Experiment by applying for Omniledger w/ the first 10 million Bitcoin transactions based on OMNeT++ simulator Result: Reduced the cross-shard txs up to 10 folds, cut the txs confirmation time by 93%, and at the same time, increase the throughput by 50%
Truc Nguyen, My T. Thai (Univ. of Florida)
Single shard flooding attack against hash-based transaction sharding
TEE-based approach to distributed transactions to shards
Implement OptChain in TEE for honest validators to agree on its output
Assume some of validators are equipped with TEES
UC Proofs